package 动态规划.backageQuestion;

/**
 *  分割等和子集
 *  给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 *  解题思路： 这个问题可以转化为一个经典的0-1背包问题的变种，在这里，我们要找到一个子集，子集中的元素总和等于整个数组中元素总和的一半。
 *  解析：
 *   1. 计算总和：首选，我们需要计算出数组nums的总和sum，如果sum是奇数，肯定不会分割为两个子集，所以返回false。如果是偶数，则继续计算。
 *   2. 定义状态：动态规划的核心是定义状态，在这个问题中，可以定义dp[i][j]为一个布尔值，表示数组从前i个元素中选择若干个是否存在一种方案
 *   使得被选取的整数的和等于j。
 *     i代表的是数组nums中的前i个元素（注意，i是从0开始的索引）
 *     j代表目标和，范围是从0到【sum/2】，其中sum是数组nums的总和。
 *   3. 状态转移方程：
 *      对于dp[i][j],有两种选择来更新它的值，选择当前元素nums[i] 或者不选择
 *      (1): 不选择nums[i]: 如果我们不选择nums[i]，那么问题就演变成了从前i-1个元素中选择若干个元素，使得它们的和等于j，即dp[i-1][j]。如果dp[i-1][j]=true,则dp[i][j]为true
 *      (2): 选择nums[i]: 如果我们要选择nums[i],那么问题就变成了从前i-1个元素中选择若干个元素，使得它们的和等于j-nums[i],所以如果j-nums[i]>=0
 *      且dp[i-1][j-nums[i]] = true, 那么dp[i][j] = true , 否则均是不选择nums[i]的情况 则： dp[i][j]=dp[i-1][j] OR dp[i−1][j−nums[i]] if j≥nums[i]
 *   4：
 *     初始化：dp[0][0] = true, 因为空集的和为0，所以空集总是可以分割为两个子集，使得这两个子集的元素和相等。
 *     返回值：dp[nums.length - 1][target], target是目标和
 * @Author lf
 * @Date 3/24/2024
 */
public class PartitionEqualSubsetSum {
    public boolean canPartition(int[] nums) {
        // 计算总和
        int sum = 0;
        for (int num : nums){
            sum+=num;
        }
        // 和为奇数没有两个相同的子集，返回false
        if(sum % 2 == 1){
            return false;
        }
        int target = sum /2;
        // 定义dp数组
        boolean[][] dp = new boolean[nums.length][target+1];
        // 初始化
        for (int i = 0; i < nums.length; i++) {
            dp[i][0] = true;
        }
        // 如果数组中的第一个元素也小于target, 那么这个元素也是子集
        if(nums[0] <= target){
            dp[0][nums[0]] = true;
        }
        for (int i = 1; i <nums.length ; i++) {
            for (int j = 1; j <= target ; j++){
                // 状态转移方程公式
                dp[i][j] = dp[i-1][j];
                if(j - nums[i] >= 0){
                    dp[i][j] = dp[i-1][j] || dp[i-1][j-nums[i]];
                }
            }
        }
        return dp[nums.length-1][target];
    }

    public static void main(String[] args) {

        System.out.println(new PartitionEqualSubsetSum().canPartition(new int[]{1,5,11,5}));
        System.out.println(new PartitionEqualSubsetSum().canPartition(new int[]{2,2,1,1}));
    }
}
